package com.yuan.algorithms.算法导论_第一部分;

/**
 * @author YouYuan <br>
 *         E-mail:1265161633@qq.com <br>
 *         创建时间：2015年11月23日 下午8:29:16 <br>
 *         说明:最大子数组的线性时间解决算法。《算法导论》4.1-5 
 *         思路： 如果a[1..j]已经得到了其最大子数组，那么a[1..j+1]最大子数组只能是两种情况 
 *         （1）a[1..j+1]的最大子数组就是a[1..j]; 
 *         （2）a[1..j+1]的最大子数组是a[i..j+1],1<=i<=j;
 *         那么，如何求得所谓的（2）中的a[i..j+1]呢？ 首先需要承认这样的事实，如果一个数组a[p..r]求和得到负值，那么数组a[p..r+1]的最大子数组肯定不会是a[p..r+1]，因为a[p..r]+a[r+1]<a[r+1].
 *         在以上程序中，我们用temp存储所谓的a[p..r]，只要a[p..r]的求和是负值，那么从下一个a[r+1]值开始，temp重新从零开始求和，只要temp > summax,就更新summax,这样，我们一次遍历后，就能得到最大的summax
 *         详细讲解：http://segmentfault.com/a/1190000000733277
 */
public class MaximumSubarray {

	public static void main(String[] args) {
		double[] arr1 = { 10, -25, 20, -23, 18, 20, -7, 12, -22, 15, -4, 7 };
		double[] arr2 = {-3, -4, -5, -1};
		findMaximumSubarray(arr2);
	}

	private static void findMaximumSubarray(double[] arr) {
		int low, hight;//最大子数组的起点和终点
		low = hight = 0;
		double maximumSubarray = -0xfffffff;//最大子数组的和
		double temp = 0;//用于记录当前数列的累加和
		boolean mark = true;//用于标记当前是否是子数组的起点
		for (int i = 0; i < arr.length; i++) {
			temp += arr[i];//累加当前元素
			if (temp > maximumSubarray) {
				//若当前序列和大于当前最大子数组，则更新最大子数组
				maximumSubarray = temp;
				if (mark) {//最大子数组的起点
					int j = i;
					for(; j > 0 && arr[j-1] >= 0; j--);//起点可以追溯到当前元素之前的最大正数序列
					low = j;//记录最大子数组的起点和终点
					hight = i;
					mark = false;//记录起点已被记录，下次更新时设置终点
				} else {
					hight = i;//更新终点
				}
			}
			if (temp < 0) {//若当前序列和为负数，则重置序列，尝试从新的起点搜索
				temp = 0;
				mark = true;
			}
		}
		System.out.println("low:"+low + " hight:" + hight + " maximumSubarray:" + maximumSubarray);
	}

}
